• What are the challenges Garry, Larry, and Harry encounter in doing their job, when working with text data?

  • Go to www.menti.com and use the code 22 07 62 0

• Huge amount of data

• High dimensional but sparse

  • all possible word and phrase types in the language!!

• Noisy data

  • Examples: Abbreviations, spelling errors, short text

• Complex relationships between words

  • “Hema merges with Intertoys”

  • “Intertoys is bought by Hema”

Back to the story

• Which can be a part of Text Mining definition?
  • The discovery by computer of new, previously unknown information from textual data
  • Automatically extracting information from text
  • Text mining is about looking for patterns in text
  • Text mining describes a set of techniques that model and structure the information content of textual sources

(You can choose multiple choices)

Go to www.menti.com and use the code 22 07 62 0

• “the discovery by computer of new, previously unknown information, by automatically extracting information from different written resources” Hearst (1999)

• Text mining is about looking for patterns in text, in a similar way that data mining can be loosely described as looking for patterns in data.

• Text mining describes a set of linguistic, statistical, and machine learning techniques that model and structure the information content of textual sources. (Wikipedia)

• You can view my screen on your machine:

  • join.me/TMPython

• Access the course materials from:

  • www.ayoubbagheri.nl/TMPython

• The course teaches students the basic and advanced text mining techniques using Python on a variety of applications in many domains of science.

• From 1 to 5 how familiar are you with Python?

  • Go to www.menti.com and use the code 81 09 57 8

• Which Python IDE do you mostly use?

  • Go to www.menti.com and use the code 81 09 57 8

• From 1 to 10 how familiar are you with Google Colab?

• Latest: Python 3.9.1

• Python For Beginners

  • https://www.python.org/about/gettingstarted/

• The Python Language Reference

  • https://docs.python.org/3/reference/

• Python 3.9.1 documentation

  • https://docs.python.org/3/

• Colaboratory, or “Colab” for short, allows you to write and execute Python in your browser, with
  • Zero configuration required
  • Free access to GPUs
  • Easy sharing
• https://colab.research.google.com/notebooks/intro.ipynb

• From 1 to 5 how familiar are you with Google Colab?

  • Go to www.menti.com and use the code 81 09 57 8

Code in Colab

• During the lecture

  • Post your question to the chat; we will read them during a break.

• During the computer lab

  • Post your question in general; we will answer them.

• After the lecture

  • Feel free to send me an email or text me in Microsoft Teams

• Text classification
• Text clustering

We will also cover:

• Sentiment analysis
• Feature selection
• Topic modelling
• Word embedding
• Deep learning models
• Responsible text mining
• Text summarization

• Supervised learning
• Human experts annotate a set of text data
  • Training set
• Learn a classification model

• Which problem is not a text classification task? (less likely to be)

  • Author’s gender detection from text

  • Finding about the smoking conditions of patients from clinical letters

  • Grouping news articles into political vs non-political news

  • Classifying reviews into positive and negative sentiment

Go to www.menti.com and use the code 86 08 86 5

• Unsupervised learning
• Finding Groups of Similar Documents
• No labeled data

• Which problem is not a text clustering task? (less likely to be)

  • Grouping similar news articles

  • Grouping discharge letters in two categories: heart disease vs cancer

  • Grouping tweets which support Trump into three undefined subgroups

  • Grouping online books of a library in 10 categories

Go to www.menti.com and use the code 86 08 86 5

• Represent documents by concept vectors

  • Each concept defines one dimension

  • \(k\) concepts define a high-dimensional space

  • Element of vector corresponds to concept weight

    • E.g., \(d=(x_1,…,x_k)\), \(x_i\) is “importance” of concept \(i\) in \(d\)

• Represent documents by concept vectors

  • Each concept defines one dimension

  • \(k\) concepts define a high-dimensional space

  • Element of vector corresponds to concept weight

    • E.g., \(d=(x_1,…,x_k)\), \(x_i\) is “importance” of concept \(i\) in \(d\)

• Distance between the vectors in this concept space

  • Relationship among documents

• All documents are projected into this concept space

• All documents are projected into this concept space

• Term as the basis for vector space

• Break a stream of text into meaningful units

  • Tokens: words, phrases, symbols

    • Input: It’s not straight-forward to perform so-called “tokenization.”

• Break a stream of text into meaningful units

  • Tokens: words, phrases, symbols

    • Input: It’s not straight-forward to perform so-called “tokenization.”

    • Output(1): ‘It’s’, ‘not’, ‘straight-forward’, ‘to’, ‘perform’, ‘so-called’, ‘“tokenization.”’

    • Output(2): ‘It’, ’’‘, ’s’, ‘not’, ‘straight’, ‘-’, ‘forward, ’to’, ‘perform’, ‘so’, ‘-’, ‘called’, ‘“‘, ’tokenization’, ‘.’, ’”‘

• Break a stream of text into meaningful units

  • Tokens: words, phrases, symbols

    • Input: It’s not straight-forward to perform so-called “tokenization.”

    • Output(1): ‘It’s’, ‘not’, ‘straight-forward’, ‘to’, ‘perform’, ‘so-called’, ‘“tokenization.”’

    • Output(2): ‘It’, ’’‘, ’s’, ‘not’, ‘straight’, ‘-’, ‘forward, ’to’, ‘perform’, ‘so’, ‘-’, ‘called’, ‘“‘, ’tokenization’, ‘.’, ’”‘

  • Definition depends on language, corpus, or even context

• Solutions

  • Regular expressions

    • []+: so-called -> ‘so’, ‘called’

    • []+: It’s -> ‘It’s’ instead of ‘It’, ‘’s’

• Solutions

  • Regular expressions

    • []+: so-called -> ‘so’, ‘called’

    • []+: It’s -> ‘It’s’ instead of ‘It’, ‘’s’

  • Statistical methods

    • Explore rich features to decide where the boundary of a word is

      • Apache OpenNLP (http://opennlp.apache.org/)

      • Stanford NLP Parser (http://nlp.stanford.edu/software/lex-parser.shtml)

    • Online Demo

      • Stanford (http://nlp.stanford.edu:8080/parser/index.jsp)

      • UIUC (http://cogcomp.cs.illinois.edu/curator/demo/index.html)

• N-grams: a contiguous sequence of N tokens from a given piece of text
  • E.g., ‘Text mining is to identify useful information.’
  • Bigrams: ‘text_mining’, ‘mining_is’, ‘is_to’, ‘to_identify’, ‘identify_useful’, ‘useful_information’, ‘information_.’

• Pros: capture local dependency and order

• Cons: a purely statistical view, increase the vocabulary size \(O(V^N)\)

• Represent a document with all the occurring words

  • Pros

    • Preserve all information in the text (hopefully)

    • Fully automatic

  • Cons

    • Vocabulary gap: cars v.s., car, talk v.s., talking

    • Large storage: N-grams needs \(𝑂(𝑉^𝑁)\)

  • Solution

    • Construct controlled vocabulary

• Zipf’s law

  • Frequency of any word is inversely proportional to its rank in the frequency table

• Zipf’s law

  • Frequency of any word is inversely proportional to its rank in the frequency table

  • Formally

    • \(f(k;s,N)=\frac{1/k^S}{\sum_{n=1}^N{1/n^S}}\)

      where \(k\) is rank of the word; \(N\) is the vocabulary size; \(s\) is language-specific parameter

• Zipf’s law

  • Frequency of any word is inversely proportional to its rank in the frequency table

  • Formally

    • \(f(k;s,N)=\frac{1/k^S}{\sum_{n=1}^N{1/n^S}}\)

      where \(k\) is rank of the word; \(N\) is the vocabulary size; \(s\) is language-specific parameter

  • Simply: \(f(k;s,N) \propto 1/k^s\)

• Zipf’s law

  • Frequency of any word is inversely proportional to its rank in the frequency table

  • Formally

    • \(f(k;s,N)=\frac{1/k^S}{\sum_{n=1}^N{1/n^S}}\)

      where \(k\) is rank of the word; \(N\) is the vocabulary size; \(s\) is language-specific parameter

  • Simply: \(f(k;s,N) \propto 1/k^s\)

Discrete version of power law

• In a large Spanish text corpus, if we know the most popular word’s frequency is 145,872, what is your best estimate of its second most popular word’s frequency?

• Split text into words and sentences

• Split text into words and sentences

• Split text into words and sentences

• Split text into words and sentences

  • Task: what is the most likely segmentation /tokenization?

• Determine text mapping to proper names

• Determine text mapping to proper names

• Determine text mapping to proper names

  • Task: what is the most likely mapping

• Annotate each word in a sentence with a part-of-speech.

• Useful for subsequent syntactic parsing and word sense disambiguation.

• Head words take large portion of occurrences, but they are semantically meaningless

  • E.g., the, a, an, we, do, to

• Head words take large portion of occurrences, but they are semantically meaningless

  • E.g., the, a, an, we, do, to

• Tail words take major portion of vocabulary, but they rarely occur in documents

  • E.g., sesquipedalianism

• Head words take large portion of occurrences, but they are semantically meaningless

  • E.g., the, a, an, we, do, to

• Tail words take major portion of vocabulary, but they rarely occur in documents

  • E.g., sesquipedalianism

• The rest is most representative

  • To be included in the controlled vocabulary

• Convert different forms of a word to a normalized form in the vocabulary

  • U.S.A. -> USA, St. Louis -> Saint Louis

• Convert different forms of a word to a normalized form in the vocabulary

  • U.S.A. -> USA, St. Louis -> Saint Louis

• Solution

  • Rule-based

    • Delete periods and hyphens

    • All in lower cases

  • Dictionary-based

    • Construct equivalent class

      • Car -> “automobile, vehicle”

      • Mobile phone -> “cellphone”

• Convert different forms of a word to a normalized form in the vocabulary

  • U.S.A. -> USA, St. Louis -> Saint Louis

• Solution

  • Rule-based

    • Delete periods and hyphens

    • All in lower cases

  • Dictionary-based

    • Construct equivalent class ← We will come back to this later

      • Car -> “automobile, vehicle”

      • Mobile phone -> “cellphone”

• Reduce inflected or derived words to their root form

  • Plurals, adverbs, inflected word forms

    • E.g., ladies -> lady, referring -> refer, forgotten -> forget

  • Bridge the vocabulary gap

• Reduce inflected or derived words to their root form

  • Plurals, adverbs, inflected word forms

    • E.g., ladies -> lady, referring -> refer, forgotten -> forget

  • Bridge the vocabulary gap

  • Solutions (for English)

    • Porter stemmer: patterns of vowel-consonant sequence

    • Krovetz stemmer: morphological rules

• Reduce inflected or derived words to their root form

  • Plurals, adverbs, inflected word forms

    • E.g., ladies -> lady, referring -> refer, forgotten -> forget

  • Bridge the vocabulary gap

  • Solutions (for English)

    • Porter stemmer: patterns of vowel-consonant sequence

    • Krovetz stemmer: morphological rules

  • Risk: lose precise meaning of the word

    • E.g., lay -> lie (a false statement? or be in a horizontal position?)

• Useless words for document analysis

  • Not all words are informative

  • Remove such words to reduce vocabulary size

• Useless words for document analysis

  • Not all words are informative

  • Remove such words to reduce vocabulary size

  • No universal definition

• Useless words for document analysis

  • Not all words are informative

  • Remove such words to reduce vocabulary size

  • No universal definition

  • Risk: break the original meaning and structure of text

    • E.g., this is not a good option -> option

    
    to be or not to be -> null

Discrete version of power law

1. Tokenization:

1. Tokenization:
D1: ‘Text’, ‘mining’, ‘is’, ‘to’, ‘identify’, ‘useful’, ‘information’, ‘.’

1. Tokenization:

D1: ‘Text’, ‘mining’, ‘is’, ‘to’, ‘identify’, ‘useful’, ‘information’, ‘.’

2. Stemming/normalization:

1. Tokenization:

D1: ‘Text’, ‘mining’, ‘is’, ‘to’, ‘identify’, ‘useful’, ‘information’, ‘.’

2. Stemming/normalization:

D1: ‘text’, ‘mine’, ‘is’, ‘to’, ‘identify’, ‘use’, ‘inform’, ‘.’

1. Tokenization:

D1: ‘Text’, ‘mining’, ‘is’, ‘to’, ‘identify’, ‘useful’, ‘information’, ‘.’

2. Stemming/normalization:

D1: ‘text’, ‘mine’, ‘is’, ‘to’, ‘identify’, ‘use’, ‘inform’, ‘.’

3. N-gram construction:

1. Tokenization:

D1: ‘Text’, ‘mining’, ‘is’, ‘to’, ‘identify’, ‘useful’, ‘information’, ‘.’

2. Stemming/normalization:

D1: ‘text’, ‘mine’, ‘is’, ‘to’, ‘identify’, ‘use’, ‘inform’, ‘.’

3. N-gram construction:

D1: ‘text-mine’, ‘mine-is’, ‘is-to’, ‘to-identify’, ‘identify-use’, ‘use-inform’, ‘inform-.’

1. Tokenization:

D1: ‘Text’, ‘mining’, ‘is’, ‘to’, ‘identify’, ‘useful’, ‘information’, ‘.’

2. Stemming/normalization:

D1: ‘text’, ‘mine’, ‘is’, ‘to’, ‘identify’, ‘use’, ‘inform’, ‘.’

3. N-gram construction:

D1: ‘text-mine’, ‘mine-is’, ‘is-to’, ‘to-identify’, ‘identify-use’, ‘use-inform’, ‘inform-.’

4. Stopword/controlled vocabulary filtering::

1. Tokenization:

D1: ‘Text’, ‘mining’, ‘is’, ‘to’, ‘identify’, ‘useful’, ‘information’, ‘.’

2. Stemming/normalization:

D1: ‘text’, ‘mine’, ‘is’, ‘to’, ‘identify’, ‘use’, ‘inform’, ‘.’

3. N-gram construction:

D1: ‘text-mine’, ‘mine-is’, ‘is-to’, ‘to-identify’, ‘identify-use’, ‘use-inform’, ‘inform-.’

4. Stopword/controlled vocabulary filtering::
D1: ‘text-mine’, ‘to-identify’, ‘identify-use’, ‘use-inform’

• Important!
• Why?
  • Corpus-wise: some terms carry more information about the document content
  • Document-wise: not all terms are equally important

• Important!
• Why?
  • Corpus-wise: some terms carry more information about the document content
  • Document-wise: not all terms are equally important
• How?
  • Two basic heuristics
    • TF (Term Frequency) = Within-doc-frequency
    • IDF (Inverse Document Frequency)

• Idea: a term is more important if it occurs more frequently in a document

• TF Formulas

  • Let \(c(t,d)\) be the frequency count of term \(t\) in doc \(d\)

  • Raw TF: \(tf(t,d) =c(t,d)\)

• Idea: a term is more important if it occurs more frequently in a document
• TF Formulas
  • Let \(c(t,d)\) be the frequency count of term \(t\) in doc \(d\)
  • Raw TF: \(tf(t,d) =c(t,d)\)

• Two views of document length
  • A doc is long because it is verbose
  • A doc is long because it has more content

• Two views of document length
  • A doc is long because it is verbose
  • A doc is long because it has more content
• Raw TF is inaccurate
  • Document length variation
  • “Repeated occurrences” are less informative than the “first occurrence”
  • Information about semantic does not increase proportionally with number of term occurrence

• Two views of document length
  • A doc is long because it is verbose
  • A doc is long because it has more content
• Raw TF is inaccurate
  • Document length variation
  • “Repeated occurrences” are less informative than the “first occurrence”
  • Information about semantic does not increase proportionally with number of term occurrence
• Generally penalize long document, but avoid over-penalizing

• Two views of document length
  • A doc is long because it is verbose
  • A doc is long because it has more content
• Raw TF is inaccurate
  • Document length variation
  • “Repeated occurrences” are less informative than the “first occurrence”
  • Information about semantic does not increase proportionally with number of term occurrence
• Generally penalize long document, but avoid over-penalizing
  • Pivoted length normalization

• Maximum TF scaling
  • \(tf(t,d) = \alpha + (1 - \alpha)\frac{c(t,d}{\underset{t}{\operatorname{max}} {c(t,d)}}\), if \(c(t,d)>0\)
  • Normalize by the most frequent word in this doc

• Maximum TF scaling
  • \(tf(t,d) = \alpha + (1 - \alpha)\frac{c(t,d}{\underset{t}{\operatorname{max}} {c(t,d)}}\), if \(c(t,d)>0\)
  • Normalize by the most frequent word in this doc

• Sub-linear TF scaling
  • \[tf(t,d)= \left\{ \begin{array}{**rcl**} 1 + logc(t,d), if \ c(t,d)>0 & \\ 0, \ \ otherwise& \end{array} \right. \]

• Idea: a term is more discriminative if it occurs only in fewer documents

• Solution
  • Assign higher weights to rare terms
    
  • Formula
    • \(IDF(t) = 1 + log(\frac{N}{df(t)})\)

• Solution
  • Assign higher weights to rare terms
    
  • Formula
    • \(IDF(t) = 1 + log(\frac{N}{df(t)})\)
    \(log\): Non-linear scaling; \(N\): total number of documents; \(df(t)\): number of docs containing term \(t\)

• Solution
  • Assign higher weights to rare terms
    
  • Formula
    • \(IDF(t) = 1 + log(\frac{N}{df(t)})\)
    \(log\): Non-linear scaling; \(N\): total number of documents; \(df(t)\): number of docs containing term \(t\)
  • A corpus-specific property
    • Independent of a single document

• If we remove one document from the corpus, how would it affect the IDF of words in the vocabulary?

• If we remove one document from the corpus, how would it affect the IDF of words in the vocabulary?
• If we add one document from the corpus, how would it affect the IDF of words in the vocabulary?

• How about total term frequency?
  • \(ttf(t) = \sum_d{c(t,d)}\)

• How about total term frequency?
  • \(ttf(t) = \sum_d{c(t,d)}\)

• Cannot recognize words frequently occurring in a subset of documents

• Combining TF and IDF
  • Common in doc → high tf → high weight
  • Rare in collection → high idf → high weight
  • \(w(t,d)=TF(t,d) \times IDF(t)\)

• Combining TF and IDF
  • Common in doc → high tf → high weight
  • Rare in collection → high idf → high weight
  • \(w(t,d)=TF(t,d) \times IDF(t)\)
• Most well-known document representation schema in IR! (G Salton et al. 1983)

• Combining TF and IDF
  • Common in doc → high tf → high weight
  • Rare in collection → high idf → high weight
  • \(w(t,d)=TF(t,d) \times IDF(t)\)
• Most well-known document representation schema in IR! (G Salton et al. 1983)

• Combining TF and IDF
  • Common in doc → high tf → high weight
  • Rare in collection → high idf → high weight
  • \(w(t,d)=TF(t,d) \times IDF(t)\)
• Most well-known document representation schema in IR! (G Salton et al. 1983)

• Euclidean distance?

• Euclidean distance
  • \(dist(d_i, d_j) = \sqrt{\sum_{t\in V}{[tf(t,d_i)idf(t) - tf(t, d_j)idf(t)]^2}}\)

• Euclidean distance
  • \(dist(d_i, d_j) = \sqrt{\sum_{t\in V}{[tf(t,d_i)idf(t) - tf(t, d_j)idf(t)]^2}}\)
  • Longer documents will be penalized by the extra words

• Euclidean distance
  • \(dist(d_i, d_j) = \sqrt{\sum_{t\in V}{[tf(t,d_i)idf(t) - tf(t, d_j)idf(t)]^2}}\)
  • Longer documents will be penalized by the extra words
  • We care more about how these two vectors are overlapped

• Angle: how vectors are overlapped
  • Cosine similarity – projection of one vector onto another

• Angle between two vectors
  • \(cosine(d_i, d_j) = \frac{V_{d_i}^TV_{d_j}}{|V_{d_i}|_2 \times |V_{d_j}|_2}\) ← TF-IDF vector

• Angle between two vectors

  • \(cosine(d_i, d_j) = \frac{V_{d_i}^TV_{d_j}}{|V_{d_i}|_2 \times |V_{d_j}|_2}\) ← TF-IDF vector

• Documents are normalized by length

• Angle between two vectors

  • \(cosine(d_i, d_j) = \frac{V_{d_i}^TV_{d_j}}{|V_{d_i}|_2 \times |V_{d_j}|_2}\) ← TF-IDF vector

• Documents are normalized by length

• Angle between two vectors

  • \(cosine(d_i, d_j) = \frac{V_{d_i}^TV_{d_j}}{|V_{d_i}|_2 \times |V_{d_j}|_2}\) ← TF-IDF vector

• Documents are normalized by length

• Empirically effective!
• Intuitive
• Easy to implement
• Well-studied/mostly evaluated
• The Smart system
  • Developed at Cornell: 1960-1999
  • Still widely used

• Empirically effective!
• Intuitive
• Easy to implement
• Well-studied/mostly evaluated
• The Smart system
  • Developed at Cornell: 1960-1999
  • Still widely used
• Warning: many variants of TF-IDF!

• Assume term independence

• Assume term independence
• Lack of “predictive adequacy”
  • Arbitrary term weighting
  • Arbitrary similarity measure

• Assume term independence
• Lack of “predictive adequacy”
  • Arbitrary term weighting
  • Arbitrary similarity measure
• Lots of parameter tuning!

• SALTClass
• ICD Classification
• ASReview